home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / files.swg / 0016_Binary Key Search - File.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-06-08  |  3.2 KB  |  87 lines
  1. {===========================================================================
  2.  BBS: Canada Remote Systems
  3. Date: 05-31-93 (20:29)             Number: 24331
  4. From: HERB BROWN                   Refer#: NONE
  5.   To: ERIC GIVLER                   Recvd: NO
  6. Subj: USERS FILE                     Conf: (1221) F-PASCAL
  7. ---------------------------------------------------------------------------
  8. On this day, <May 28 17:32>, Eric Givler (1:270/101.15@fidonet) noted:
  9.  EG> How would this help?  You'd still have to search the entire
  10.  EG> INDEX file LINEARLY, correct?  Or would you have the INDEX sorted?
  11.  EG> If so, how would you keep it sorted?  More input would REALLY be
  12.  EG> appreciated!
  13.  
  14. This is code for a binary "split and search" method.   Anyways, thats just
  15. something I call it.  Actually, it's a rudimentary binary search.
  16.  
  17. Suppose you had a key record of                                           }
  18.  
  19.  key = record
  20.  reference : Longint;  { room for a lot of records }
  21.  KeySearchField : String30; { The key string to be stored}
  22.  end;     { Note, several smaller strings could be put together to make the
  23.             search critical, i.e., keysearchField:=First+second+ThirdName;
  24.             As long as the field length stays less than or equal to what you
  25.          defined }
  26.  
  27. {Then using a function that would return a boolean value, i.e., true if data
  28. matches, false if not found, then it would look like so.. }
  29.  
  30. Function FindKey( VAR  AKey : AKeyFile;
  31.                   VAR  AKeyRef : Longint;
  32.                        FindMe : String80): Boolean;
  33.  
  34. VAR High,Low,Mid : Longint;  { For collision processing }
  35.      Target : Key;
  36.      Gotit  : Boolean;
  37.      Collison : Boolean;
  38.      NumRecs  : Longint;
  39.  
  40.  
  41. begin
  42.  AKeyRef :=0;
  43.  NumRecs := FileSize(AKey);  {Get the number of records stored in file}
  44.  
  45.  High := NumRecs;
  46.  Low := 0;
  47.  Mid := (Low + High) DIV 2 { Split point }
  48.  FindKey := False;
  49.  Gotit := False;
  50.  Collision := False;
  51.  If NumRecs > 0 Then {the file is not empty }
  52.   Repeat
  53.    Seek(AKey,Mid);
  54.    Read(Akey,Target);
  55.    {Was there a position collision ??}
  56.    IF (Low = Mid) OR (High = Mid) the Collision := True;
  57.      IF Findme := Target.KeySearchField Then { Yay ! }
  58.          begin
  59.           Gotit := True;
  60.           FindKey := True;
  61.           AKeyRef := Target.Reference;
  62.         End
  63.     Else  { Divide in half and try it again..}
  64.      Begin
  65.       If FindMe > Target.KeySearchField then Low := Mid
  66.        Else High := Mid;
  67.       Mid := (Low + High + 1) DIV 2;
  68.       AKeyRef := Mid
  69.     End
  70.  Until Collision or Gotit;
  71. End;
  72.  
  73. (*
  74. This is a working example.  There are some minor precautions that need to be
  75. noted, though.   This will only work on sorted data, for one.  The data can be
  76. sorted with a Quick Sort and the key file re-written in sorted order.   The
  77. advantage here is the actual data file need not be sorted at all.
  78.  
  79. Any time you work with a data base, get into the habit of ALWAYS including a
  80. deleted tag field.  The above example lacks this, though.
  81.  
  82. This is just one of many ways of searching a database.  Professional <grin>
  83. applications would probably be better suited for AVL trees or Btrees.
  84.  
  85. Building an array "cache" helps speed up processing as well.  That is whole
  86. 'nuder ball game, though.. *)
  87.